package com.demo.java.OD451_500.OD452;

import java.util.*;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【5G 网络建设(C&D卷)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146336754
 */
public class OdMain {
    // 并查集，记录每个基站的父节点
    static int[] parents;

    // 查找操作，返回元素的根节点
    public static int find(int x) {
        if (parents[x] != x) {
            parents[x] = find(parents[x]);
        }
        return parents[x];
    }

    // 合并操作，将两个基站连接在一起
    public static void union(int x, int y) {
        parents[find(x)] = find(y);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取基站数量 N 和已连接边的数量 M
        int N = scanner.nextInt();
        int M = scanner.nextInt();

        // 初始化并查集，父节点初始化为自己
        parents = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            parents[i] = i;
        }

        int edgeNum = 0;  // 已连接的边的数量
        List<int[]> edges = new ArrayList<>();

        // 处理已建立的连接
        for (int i = 0; i < M; i++) {
            int X = scanner.nextInt();  // 基站 X
            int Y = scanner.nextInt();  // 基站 Y
            int Z = scanner.nextInt();  // 连接费用
            int P = scanner.nextInt();  // 是否已建立连接（1为已连接，2为未连接）

            if (P == 1) {  // 如果已经连接，直接合并基站
                if (find(X) != find(Y)) {
                    union(X, Y);
                    edgeNum++;
                }
            } else {  // 如果没有连接，记录下来
                edges.add(new int[]{Z, X, Y});
            }
        }

        // 将剩余的边按照费用 Z 进行升序排序
        edges.sort(Comparator.comparingInt(o -> o[0]));

        int ans = 0;

        // 使用 Kruskal 算法构建最小生成树
        for (int[] edge : edges) {
            int Z = edge[0];  // 连接费用
            int X = edge[1];  // 基站 X
            int Y = edge[2];  // 基站 Y

            if (find(X) != find(Y)) {  // 如果 X 和 Y 不在同一集合，进行合并
                union(X, Y);
                ans += Z;  // 累加当前连接的费用
                edgeNum++;

                if (edgeNum == N - 1) {  // 如果已经连接了 N - 1 条边，停止
                    break;
                }
            }
        }

        // 如果已经连接了 N - 1 条边，输出最小费用；否则输出 -1
        System.out.println(edgeNum == N - 1 ? ans : -1);
    }
}